#include <stdio.h>
#include <stdlib.h>
//图的应用之关键路径(带权有向图)
#define MAXSIZE 100
#define MAX 0x7fffffff
typedef struct 
{
    int vertex[MAXSIZE];
    int edgeweight[MAXSIZE][MAXSIZE];
    int vertex_num;
    int edge_num;
}mat_graph;
void creatgraph(mat_graph *g)
{
    g->vertex_num=10;
    g->edge_num=13;
    int i,j;
    for(i=0;i<g->vertex_num;i++)
    {
        g->vertex[i]=i;
    }
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<g->vertex_num;j++)
        {
            g->edgeweight[i][j]=MAX;
        }
    }
    g->edgeweight[0][1]=3;
    g->edgeweight[0][2]=4;
    g->edgeweight[1][3]=5;
    g->edgeweight[1][4]=6;
    g->edgeweight[2][3]=8;
    g->edgeweight[2][5]=7;
    g->edgeweight[3][4]=3;
    g->edgeweight[4][6]=9;
    g->edgeweight[4][7]=4;
    g->edgeweight[5][7]=6;
    g->edgeweight[6][9]=2;
    g->edgeweight[7][8]=5;
    g->edgeweight[8][9]=3;
}
//邻接表的边节点
typedef struct Edgenode
{
    int edge_ver;
    int edge_weight;
    struct Edgenode *next;
}edgenode;
//邻接表的头节点
typedef struct 
{
    int in;
    int data;
    edgenode *head;
}vertexnode;
//邻接表
typedef struct 
{
    vertexnode *data;
    int vertex_num;
    int edge_num;
}adj_graph;
void creatadjgraph(mat_graph *g,adj_graph **adj)
{   
    *adj=(adj_graph *)malloc(sizeof(adj_graph));
    (*adj)->data=(vertexnode *)malloc(sizeof(vertexnode)*MAXSIZE);
    (*adj)->vertex_num=g->vertex_num;
    (*adj)->edge_num=g->edge_num;
    int i,j;
    for(i=0;i<g->vertex_num;i++)
    {
        (*adj)->data[i].in=0;
        (*adj)->data[i].data=g->vertex[i];
        (*adj)->data[i].head=NULL;
    }
    edgenode *e;
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<g->vertex_num;j++)
        {
            if(g->edgeweight[i][j]!=MAX)
            {
                e=(edgenode *)malloc(sizeof(edgenode));
                e->edge_ver=(*adj)->data[j].data;
                e->edge_weight=g->edgeweight[i][j];
                e->next=(*adj)->data[i].head;
                (*adj)->data[i].head=e;
                (*adj)->data[j].in++;
            }
        }
    }
}
int top=-1;
int stack[MAXSIZE]={0};
int stack2[MAXSIZE]={0};
int top2=-1;
void aoe(adj_graph *adj)
{
    int etv[MAXSIZE]={0};//最早发生时间
    int ltv[MAXSIZE];//最晚发生时间
    int i,k;
    for(i=0;i<adj->vertex_num;i++)
    {
        if(adj->data[i].in==0)
        {
            top++;
            stack[top]=adj->data[i].data;
        }
        edgenode *e;
        while(top!=-1)
        {
            k=stack[top];
            top--;
            printf("V%d->",k);
            top2++;
            stack2[top2]=k;
            e=adj->data[k].head;
            while(e!=NULL)
            {   
                adj->data[e->edge_ver].in--;
                if(adj->data[e->edge_ver].in==0)
                {
                    top++;
                    stack[top]=adj->data[e->edge_ver].data;
                }
                if(etv[k]+e->edge_weight>etv[e->edge_ver])
                {
                    etv[e->edge_ver]=etv[k]+e->edge_weight;
                }
                e=e->next;
            }
        }
        printf("\n");
        printf("etv:");
        for(i=0;i<adj->vertex_num;i++)
        {
            printf("%d ",etv[i]);
        }
        printf("\n");
        for(i=0;i<adj->vertex_num;i++)
        {
            ltv[i]=etv[adj->vertex_num-1];
        }
        while(top2!=-1)
        {
            k=stack2[top2];
            top2--;
            e=adj->data[k].head;
            while(e!=NULL)
            {
                if(ltv[e->edge_ver]-e->edge_weight<ltv[k])
                {
                    ltv[k]=ltv[e->edge_ver]-e->edge_weight;
                }
                e=e->next;
            }
        }
        printf("ltv:");
        for(i=0;i<adj->vertex_num;i++)
        {
            printf("%d ",ltv[i]);
        }
        printf("\n");
        for(i=0;i<adj->vertex_num;i++)
        {
            if(etv[i]==ltv[i])
            {
                printf("v%d->",i);
            }
        }
    }
}
int main()
{
    mat_graph g;
    creatgraph(&g);
    adj_graph *adj;
    creatadjgraph(&g,&adj);
    aoe(adj);
    return 0;
}
//输出：
//V0->V1->V2->V3->V4->V6->V5->V7->V8->V9->
//etv:0 3 4 12 15 11 24 19 24 27
//ltv:0 7 4 12 15 13 25 19 24 27
//v0->v2->v3->v4->v7->v8->v9->
